#!/usr/bin/env python
# _*_coding:utf-8_*_

"""
链表
@Time : 2022/1/29 15:59
@Author: RunAtWorld
@File: link_list.py
"""


class ListNode:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

    def __str__(self):
        return str(self.val)


def traverse_iter(head: ListNode):
    """
    迭代遍历链表
    """
    while head:
        # 访问节点
        print(head.val)
        head = head.next


def traverse_recursive(head: ListNode):
    """
    递归遍历链表
    """
    if not head:
        return
    # 前序访问位置
    print(head.val)
    traverse_recursive(head.next)
    # 后序访问位置


def traverse_reverse(head: ListNode):
    """
    倒序打印链表: 在 traverse 的基础上，在后序遍历的位置输出
    """
    if not head:
        return
    traverse_reverse(head.next)
    # 后序访问
    print(head.val)


if __name__ == '__main__':
    n5 = ListNode(5)
    n4 = ListNode(4, n5)
    n3 = ListNode(3, n4)
    n2 = ListNode(2, n3)
    n1 = ListNode(1, n2)
    traverse_iter(n1)
    print("===")
    traverse_recursive(n1)
    print("倒序打印:")
    traverse_reverse(n1)
